#pragma once
#include <iostream>
#include <vector>
using namespace std;

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return 
			(size_t)key;  //转成数字，把key
	}
};


// 特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};



namespace open_address
{
	enum State
	{
		EXIST, // 0 该值存在的标记
		EMPTY, // 1 初始化的标记
		DELETE // 2  删去之后的标记
	};

	template <class K, class  V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY; //状态表示的标记
	};

	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first)) return false; //防止数据冗余
			//扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				////_tables.resize(_tables.size() * 2);
				//vector<HashData<K, V>> newTables(_tables.size() * 2);
				////遍历旧表，将所有数据映射到新表
				//_tables.swap(newTables); //该方法不好，当冲突的时候，用+1的方法时，得重写下面构造

				//遍历创建新影身，复用Insert
				// 此处只需将有效元素搬移到新哈希表中
				// 已删除的元素不用处理
				HashTable<K, V, Hash>newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++) {
					if (_tables[i]._state == EXIST) newHT.Insert(_tables[i]._kv);
				}
				_tables.swap(newHT._tables);
			}

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST) { //若存在，则表示出现了哈希冲突
				++hashi;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size(); //算在表里的位置
			while (_tables[hashi]._state != EMPTY) 
			{ //之所以用不等于ENPTY，而不是EXIST，是因为避免查找的数出现过哈希冲突之后，位置移动，然后前面的数被删，比如：
			  // 11(EXIST) 21（DELETE）31（key） 41(EXIST)
				if (_tables[hashi]._state == EXIST &&
					_tables[hashi]._kv.first == key) {
					return &_tables[hashi];
				}
				
				++hashi;
				hashi %= _tables.size(); //防止越界
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr) return false;
			else {
				ret->_state = DELETE;
				return true;
			}
		}

	private:
		vector<HashData<K, V>> _tables; //不用构建析构，因为vector本身就有析构
		size_t _n;
	};


	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}
		ht.Insert({ 19, 19 });
		ht.Insert({ 19,190 });

		cout << ht.Find(24) << endl;
		ht.Erase(4);
		cout << ht.Find(24) << endl;
		cout << ht.Find(4) << endl;

		ht.Insert({ 4,4 });
	}

	struct StringHashFunc
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash *= 31;
				hash += e;
			}
			return hash;
		}
	};

	void TestHT2()
	{
		//HashTable<string, string, StringHashFunc> ht; //但是注释第三个，则会出现“类型强制转换” : 无法从“const K”转换为“size_t”
		HashTable<string, string> ht; //使用特化，就可以支持该操作



		ht.Insert({ "sort", "排序" });
		ht.Insert({ "left", "左边" });

		//string s1("sort");
		//string s2("sort");

		cout << StringHashFunc()("bacd") << endl;
		cout << StringHashFunc()("abcd") << endl;
		cout << StringHashFunc()("aadd") << endl;
	}
}



namespace hash_bucket  //哈希桶-链式
{
	template<class T> //用一个值来确定底层存的是什么
	struct HashNode
	{
		/*pair<K, V> _kv;
		HashNode<K, V>* _next;*/

		T _data;
		HashNode<T>* _next;

		HashNode(const T&data)
			: _data(data)
			, _next(nullptr)
		{}
	};

	//前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, KeyOfT, Hash> Self;

		Node* _node;
		HashTable<K, T, KeyOfT, Hash>* _pht; //由于向上找不到，老是会报_pht找不到，因此我们需要加个前置声明

		HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}

		Self& operator++()
		{
			if (_node->_next) //当前桶还有节点
			{ 
				_node = _node->_next;
			}
			else //当前桶遍历完毕，找下一个不为空的桶
			{
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size()) //由于pht要访问其成员私有，但是无法访问，我们解决方法就是提法gettable或者提供友元
				{
					if (_pht->_tables[hashi]) 
						break; //找到不为空的桶 
					++hashi;
				}
				if (hashi == _pht->_tables.size()) //说明已经走完
				{
					_node = nullptr;
				}
				else _node = _pht->_tables[hashi];
			}
			return *this;
		}

		/*Self& operator--()
		{

		}*/


	};

	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
		//友元声明
		template<class K, class T, class KeyOfT, class Hash> //普通类的友元直接友元声明即可，而类模板需要把模板参数带上
		friend struct HTIterator;

		typedef HashNode<T> Node;
	
	public:
		typedef HTIterator<K, T, KeyOfT, Hash> Iterator;

		Iterator Begin()
		{
			if (_n == 0) return End(); //如果没有数据
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}



	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{ // 依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}


		bool Insert(const T& data) //使用的是头插
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();
			//负载因子 == 1扩容，
			// 越低，空间效率越低，时间效率越高
			///越高，空间效率越高，时间效率越低
			if (_n == _tables.size())
			{

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur) 
					{ 
						Node* next = cur->_next;
						//旧表中节点，挪动新表重新映射的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						//头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);

			}

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return true;
		}

		Node* find(const K& key)
		{
			KeyOfT kot;

			Hash hs;
			size_t hashi = hs(key) % _tables.szie();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key) return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) //如果是第一个节点 
					{
						_tables[hashi] = cur->_next;
					}
					else //否则，则让前一个指向我的后一个
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;  
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指针数组，数组的每个位置存的是指针
		size_t _n; //表中存储数据个数
	};

}